{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Spending After Buying Items"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSpending"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #购买物品的最大开销"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始大小为&nbsp;<code>m * n</code>&nbsp;的整数矩阵&nbsp;<code>values</code>&nbsp;，表示&nbsp;<code>m</code>&nbsp;个不同商店里&nbsp;<code>m * n</code>&nbsp;件不同的物品。每个商店有 <code>n</code>&nbsp;件物品，第&nbsp;<code>i</code>&nbsp;个商店的第 <code>j</code>&nbsp;件物品的价值为&nbsp;<code>values[i][j]</code>&nbsp;。除此以外，第&nbsp;<code>i</code>&nbsp;个商店的物品已经按照价值非递增排好序了，也就是说对于所有&nbsp;<code>0 &lt;= j &lt; n - 1</code>&nbsp;都有&nbsp;<code>values[i][j] &gt;= values[i][j + 1]</code>&nbsp;。</p>\n",
    "\n",
    "<p>每一天，你可以在一个商店里购买一件物品。具体来说，在第&nbsp;<code>d</code>&nbsp;天，你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择商店&nbsp;<code>i</code>&nbsp;。</li>\n",
    "\t<li>购买数组中最右边的物品&nbsp;<code>j</code>&nbsp;，开销为&nbsp;<code>values[i][j] * d</code>&nbsp;。换句话说，选择该商店中还没购买过的物品中最大的下标&nbsp;<code>j</code>&nbsp;，并且花费&nbsp;<code>values[i][j] * d</code>&nbsp;去购买。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意</strong>，所有物品都视为不同的物品。比方说如果你已经从商店 <code>1</code>&nbsp;购买了物品&nbsp;<code>0</code>&nbsp;，你还可以在别的商店里购买其他商店的物品&nbsp;<code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回购买所有 <code>m * n</code>&nbsp;件物品需要的 <strong>最大开销</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>values = [[8,5,2],[6,4,1],[9,7,3]]\n",
    "<b>输出：</b>285\n",
    "<b>解释：</b>第一天，从商店 1 购买物品 2 ，开销为 values[1][2] * 1 = 1 。\n",
    "第二天，从商店 0 购买物品 2 ，开销为 values[0][2] * 2 = 4 。\n",
    "第三天，从商店 2 购买物品 2 ，开销为 values[2][2] * 3 = 9 。\n",
    "第四天，从商店 1 购买物品 1 ，开销为 values[1][1] * 4 = 16 。\n",
    "第五天，从商店 0 购买物品 1 ，开销为 values[0][1] * 5 = 25 。\n",
    "第六天，从商店 1 购买物品 0 ，开销为 values[1][0] * 6 = 36 。\n",
    "第七天，从商店 2 购买物品 1 ，开销为 values[2][1] * 7 = 49 。\n",
    "第八天，从商店 0 购买物品 0 ，开销为 values[0][0] * 8 = 64 。\n",
    "第九天，从商店 2 购买物品 0 ，开销为 values[2][0] * 9 = 81 。\n",
    "所以总开销为 285 。\n",
    "285 是购买所有 m * n 件物品的最大总开销。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>values = [[10,8,6,4,2],[9,7,5,3,2]]\n",
    "<b>输出：</b>386\n",
    "<b>解释：</b>第一天，从商店 0 购买物品 4 ，开销为 values[0][4] * 1 = 2 。\n",
    "第二天，从商店 1 购买物品 4 ，开销为 values[1][4] * 2 = 4 。\n",
    "第三天，从商店 1 购买物品 3 ，开销为 values[1][3] * 3 = 9 。\n",
    "第四天，从商店 0 购买物品 3 ，开销为 values[0][3] * 4 = 16 。\n",
    "第五天，从商店 1 购买物品 2 ，开销为 values[1][2] * 5 = 25 。\n",
    "第六天，从商店 0 购买物品 2 ，开销为 values[0][2] * 6 = 36 。\n",
    "第七天，从商店 1 购买物品 1 ，开销为 values[1][1] * 7 = 49 。\n",
    "第八天，从商店 0 购买物品 1 ，开销为 values[0][1] * 8 = 64 。\n",
    "第九天，从商店 1 购买物品 0 ，开销为 values[1][0] * 9 = 81 。\n",
    "第十天，从商店 0 购买物品 0 ，开销为 values[0][0] * 10 = 100 。\n",
    "所以总开销为 386 。\n",
    "386 是购买所有 m * n 件物品的最大总开销。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m == values.length &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= n == values[i].length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= values[i][j] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>values[i]</code>&nbsp;按照非递增顺序排序。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-spending-after-buying-items](https://leetcode.cn/problems/maximum-spending-after-buying-items/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-spending-after-buying-items](https://leetcode.cn/problems/maximum-spending-after-buying-items/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[8,5,2],[6,4,1],[9,7,3]]', '[[10,8,6,4,2],[9,7,5,3,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        q = []\n",
    "        m, n = len(values), len(values[0])\n",
    "        for i in range(m):\n",
    "            heappush(q, (values[i][-1], i, n-1))\n",
    "        ans, d = 0, 1\n",
    "        while q:\n",
    "            cur, r, c = heappop(q)\n",
    "            ans += cur * d\n",
    "            if c > 0:\n",
    "                heappush(q, (values[r][c-1], r, c-1))\n",
    "            d += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        ans, mn = 0, len(values) * len(values[0]) + 1\n",
    "        for i in range(1, mn):\n",
    "            values.sort(key = lambda x : x[-1])\n",
    "            ans += values[0][-1] * i\n",
    "            if len(values[0]) == 1: values.pop(0)\n",
    "            else: values[0].pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        step = 1\n",
    "        hp = []\n",
    "        for i in range(len(values)):\n",
    "            arr = values[i]\n",
    "            hp.append([arr.pop(),i])\n",
    "        heapq.heapify(hp)\n",
    "\n",
    "        while len(hp)!=0:\n",
    "            popped = heapq.heappop(hp)\n",
    "            v = popped[0] #商品价值\n",
    "            idx = popped[1] #来自哪家商店\n",
    "            ret += v*step\n",
    "            step += 1\n",
    "            if len(values[idx])>0:\n",
    "                heapq.heappush(hp,[values[idx].pop(),idx])\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        m, n = len(values), len(values[0])\n",
    "        q = [(row.pop(), i) for i, row in enumerate(values)]\n",
    "        heapify(q)\n",
    "        total, c = 0, 1\n",
    "        while q:\n",
    "            value, i = heappop(q)\n",
    "            total += value * c\n",
    "            c += 1\n",
    "            if values[i]:\n",
    "                heappush(q, (values[i].pop(), i))\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        h=[]\n",
    "        n=len(values)\n",
    "        for i in range(n):\n",
    "            h.append([values[i].pop(),i])\n",
    "        heapify(h)\n",
    "        ans=0\n",
    "        d=0\n",
    "        while len(h)>0:\n",
    "            d+=1\n",
    "            a=heappop(h)\n",
    "            ans+=a[0]*d\n",
    "            if len(values[a[1]])>0:\n",
    "                heappush(h,[values[a[1]].pop(),a[1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        m, n = len(values), len(values[0])\n",
    "\n",
    "        pq = [(values[i][n - 1], i, n - 1) for i in range(m)]\n",
    "        heapify(pq)\n",
    "        \n",
    "        res, d = 0, 1\n",
    "        \n",
    "        while pq:\n",
    "            val, i, j = heappop(pq)\n",
    "            res += val * d\n",
    "            d += 1\n",
    "            if j - 1 >= 0:\n",
    "                heappush(pq, (values[i][j - 1], i, j - 1))\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        m, n = len(values), len(values[0])\n",
    "        pq = [(values[i][-1], i, n) for i in range(m)]\n",
    "        heapq.heapify(pq)\n",
    "        res = 0\n",
    "        for d in range(1, m * n + 1):\n",
    "            v, r, c = heapq.heappop(pq)\n",
    "            res, c = res + d * v, c - 1\n",
    "            if c:\n",
    "                heapq.heappush(pq, (values[r][c - 1], r, c))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        ls=[]\n",
    "        for v in values:\n",
    "            ls+=v\n",
    "        ls.sort()\n",
    "        ret=0\n",
    "        for i in range(len(ls)):\n",
    "            ret+=(i+1)*ls[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSpending(self, values: List[List[int]]) -> int:\n",
    "        final_values = []\n",
    "        for i in values:\n",
    "            final_values += i\n",
    "        final_values.sort()\n",
    "        res = 0\n",
    "        for idx,val in enumerate(final_values):\n",
    "            res += (idx+1) * val\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
